package leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Day21 {
    public static int majorityElement(int[] nums) {
            int n=nums.length;
            int x=n/2;
            int ret=0;
            if(n==1){
            return nums[0];
            }
            Map<Integer,Integer> map=new HashMap<>();
            for (int num:nums){
                if(map.get(num)==null){
                    map.put(num,1);
                }else {
                    int tmp=map.get(num)+1;
                    map.put(num,tmp);
                    if (tmp>x){
                        ret=num;
                    }
                }

            }
            return ret;
    }
    public void rotate(int[] nums, int k) {
        int n=nums.length;
        if(n==1){
            return;
        }
        if(k>n){
            k=k%n;
        }
        int[] arr=Arrays.copyOfRange(nums,n-k,n);
        for(int i=n-1;i>=k;i--){
            nums[i]=nums[i-k];
        }
        for(int i=0;i<k;i++){
            nums[i]=arr[i];
        }
    }
    /*
    * 最大子数组
    * */
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n+1];
        dp[0]=0;
        for(int i=1;i<=n;i++){
            dp[i]=Math.max(nums[i-1],dp[i-1]+nums[i-1]);
        }
        int max=Integer.MIN_VALUE;
        for(int i=1;i<=n;i++){
            if(dp[i]>max){
                max=dp[i];
            }
        }
        return max;
    }
    /*
    * 环形子数组最大和
    * */
    public int maxSubarraySumCircular(int[] nums) {
        int n=nums.length;
        int[] g=new int[n+1];
        int[] j=new int[n+1];
        for(int i=1;i<=n;i++){
            g[i]=Math.max(nums[i-1],g[i-1]+nums[i-1]);
            j[i]=Math.min(nums[i-1],j[i-1]+nums[i-1]);
        }
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        for(int i=1;i<=n;i++){
            if(g[i]>max){
                max=g[i];
            }
            if(j[i]<min){
                min=j[i];
            }
        }
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }
        if(sum==min){
            return max;
        }else{
            return Math.max(max,sum-min);
        }
    }
    public static void main(String[] args) {
        int[] arr={1,2,3,4,5,6,7};


    }
}
